﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using DO.Clustering;

namespace BLL.Clustering
{
    public class MinSpanTreeClusterManager
    {
        public static Dictionary<int,List<int>> BuildClusters(
            Dictionary<int, Dictionary<int, double>> entityDistances,
            Dictionary<int, Dictionary<int, FeatureFreq>> docFeatFreqs,
            Dictionary<int, double> termWeights)
        {
            int docCount = docFeatFreqs.Count;
            List<int> processedDocIDs=new List<int>();
            List<int> orphanDocIDs=new List<int>();
            Dictionary<int,List<int>> clusteredDocs=new Dictionary<int, List<int>>();

            Dictionary<double, List<string>> distanceDocPairs = 
                IndexDocPairsByDistance(entityDistances);
            List<double> distances=new List<double>();
            distances.AddRange(distanceDocPairs.Keys);
            distances.Sort();
            foreach(double distance in distances)
            {
                List<string> docPairs = distanceDocPairs[distance];
                foreach(string docPair in docPairs)
                {
                    string[] pair = docPair.Split(new char[] {':'});
                    int docID1 = int.Parse(pair[0]);
                    int docID2 = int.Parse(pair[1]);
                    if(!processedDocIDs.Contains(docID1))
                    {
                        Grow(
                            clusteredDocs, entityDistances, orphanDocIDs,
                            docCount, docID1);
                        processedDocIDs.Add(docID1);
                    }
                    if (!processedDocIDs.Contains(docID2))
                    {
                        Grow(clusteredDocs, entityDistances, orphanDocIDs,
                            docCount, docID2);
                        processedDocIDs.Add(docID2);
                    }
                }
            }

            if(orphanDocIDs.Count>0)
            {
                foreach(int orphanDocID in orphanDocIDs)
                {
                    List<int> orphanClusterDocIDs=new List<int>();
                    orphanClusterDocIDs.Add(orphanDocID);
                    int newClusterID = NextClusterID(clusteredDocs);
                    clusteredDocs.Add(newClusterID, orphanClusterDocIDs);
                }
            }

            return clusteredDocs;
        }

        private static Dictionary<double,List<string>> IndexDocPairsByDistance(Dictionary<int,Dictionary<int,double>> entityDistances)
        {
            Dictionary<double, List<string>> distanceDocPairs = new Dictionary<double, List<string>>();
            List<int> docIDs = new List<int>();
            docIDs.AddRange(entityDistances.Keys);
            for (int i = 0; i < docIDs.Count; i++)
            {
                int fromDocID = docIDs[i];
                for (int k = i + 1; k < docIDs.Count; k++)
                {
                    int toDocID = docIDs[k];
                    string docPair = string.Format("{0}:{1}", fromDocID, toDocID);
                    if (toDocID < fromDocID)
                        docPair = string.Format("{0}:{1}", toDocID, fromDocID);
                    double distance = entityDistances[fromDocID][toDocID];
                    if (distanceDocPairs.ContainsKey(distance))
                    {
                        List<string> docPairs = distanceDocPairs[distance];
                        docPairs.Add(docPair);
                        distanceDocPairs[distance] = docPairs;
                    }
                    else
                    {
                        List<string> docPairs = new List<string>();
                        docPairs.Add(docPair);
                        distanceDocPairs.Add(distance, docPairs);
                    }
                }
            }
            return distanceDocPairs;
        }

        private static double GetEntropy(
            Dictionary<int,List<int>> existingClusters,
            Dictionary<int,Dictionary<int,double>> entityDistances,
            int totalDocs)
        {
            double entropy = 0;
            int includedDocCount = 0;
            foreach(int existClusterID in existingClusters.Keys)
            {
                List<int> includedDocIDs = existingClusters[existClusterID];
                includedDocCount += includedDocIDs.Count;
                double diameter = DistanceManager.GetClusterDiameter(existingClusters[existClusterID], entityDistances);
                entropy += ((double)(includedDocIDs.Count - 1)) / diameter;
            }
            entropy = entropy*includedDocCount/totalDocs/existingClusters.Count;
            return entropy;
        }

        private static bool Grow(
            Dictionary<int,List<int>> existingClusters,
            Dictionary<int, Dictionary<int, double>> entityDistances,
            List<int> orphanDocIDs,
            int totalDocCount, int newDocID)
        {
            double oldEntropy = GetEntropy(existingClusters, entityDistances, totalDocCount);
            double compactChangeForNewCluster = 0;
            int existingOrphanDocID = 0;
            foreach(int orphanDocID in orphanDocIDs)
            {
                List<int> newClusteredDocs=new List<int>();
                newClusteredDocs.Add(orphanDocID);
                newClusteredDocs.Add(newDocID);
                double diameter = DistanceManager.GetClusterDiameter(newClusteredDocs, entityDistances);
                double newCompact = 1.0/diameter;
                if (newCompact > compactChangeForNewCluster)
                {
                    compactChangeForNewCluster = newCompact;
                    existingOrphanDocID = orphanDocID;
                }
            }

            double compactChangeForExistingCluster = 0;
            int existingClusterID = 0;
            foreach(int clusterID in existingClusters.Keys)
            {
                List<int> clusteredDocIDs = new List<int>();
                clusteredDocIDs.AddRange(existingClusters[clusterID]);
                double oldDiameter = DistanceManager.GetClusterDiameter(clusteredDocIDs, entityDistances);
                double oldCompact = (double) (clusteredDocIDs.Count - 1)/oldDiameter;
                clusteredDocIDs.Add(newDocID);
                Debug.Assert(!existingClusters[clusterID].Contains(newDocID));
                double newDiameter = DistanceManager.GetClusterDiameter(clusteredDocIDs, entityDistances);
                double newCompact = (double) (clusteredDocIDs.Count - 1)/newDiameter;
                if (newCompact - oldCompact > compactChangeForExistingCluster)
                {
                    compactChangeForExistingCluster = newCompact - oldCompact;
                    existingClusterID = clusterID;
                }
            }

            if(compactChangeForExistingCluster >0 && compactChangeForExistingCluster > compactChangeForNewCluster)
            {
                if (existingClusters.ContainsKey(existingClusterID))
                {
                    List<int> clusteredDocIDs = existingClusters[existingClusterID];
                    clusteredDocIDs.Add(newDocID);
                    existingClusters[existingClusterID] = clusteredDocIDs;
                    double newEntropy = GetEntropy(existingClusters, entityDistances, totalDocCount);
                    if (newEntropy <= oldEntropy)
                    {
                        clusteredDocIDs.Remove(newDocID);
                        existingClusters[existingClusterID] = clusteredDocIDs;
                        orphanDocIDs.Add(newDocID);
                        return false;
                    }
                    else
                        return true;
                }
                else
                {
                    orphanDocIDs.Add(newDocID);
                    return false;
                }
            }
            else if(compactChangeForNewCluster>0 && compactChangeForNewCluster > compactChangeForExistingCluster)
            {
                if(orphanDocIDs.Contains(existingOrphanDocID))
                {
                    int newClusterID = NextClusterID(existingClusters);
                    List<int> docIDs=new List<int>();
                    docIDs.Add(existingOrphanDocID);
                    docIDs.Add(newDocID);
                    existingClusters.Add(newClusterID, docIDs);
                    double newEntropy = GetEntropy(existingClusters, entityDistances, totalDocCount);
                    if (newEntropy <= oldEntropy)
                    {
                        existingClusters.Remove(newClusterID);
                        orphanDocIDs.Add(newDocID);
                        return false;
                    }
                    else
                    {
                        orphanDocIDs.Remove(existingOrphanDocID);
                        return true;
                    }
                }
                else
                {
                    orphanDocIDs.Add(newDocID);
                    return false;
                }
            }
            else
            {
                orphanDocIDs.Add(newDocID);
                return false;
            }
        }

        private static int NextClusterID(Dictionary<int,List<int>> clusteredDocs)
        {
            int lastID = 0;
            foreach(int clusterID in clusteredDocs.Keys)
            {
                if (clusterID > lastID)
                    lastID = clusterID;
            }
            return lastID + 1;
        }
    }
}
